package leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : zx
 * @version V1.0
 */
public class Codec {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int x) { val = x; }
    }


    public static String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

//    public static TreeNode deserialize(String data) {
//        if(data.equals("[]")) return null;
//        String[] vals = data.substring(1, data.length() - 1).split(",");
//        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
//        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{ add(root); }};
//        int i = 1;
//        while(!queue.isEmpty()) {
//            TreeNode node = queue.poll();
//            if(!vals[i].equals("null")) {
//                node.left = new TreeNode(Integer.parseInt(vals[i]));
//                queue.add(node.left);
//            }
//            i++;
//            if(!vals[i].equals("null")) {
//                node.right = new TreeNode(Integer.parseInt(vals[i]));
//                queue.add(node.right);
//            }
//            i++;
//        }
//        return root;
//    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if (data.length() == 2) {
            return null;
        }

        // 去除收尾的中括号字符
        data = data.substring(1, data.length() - 1);
        // 利用逗号分隔符获取每一个节点的值
        String[] vals = data.split(",");
        // 定义队列存储每一个有效节点，为了构建其左右子节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
        queue.offer(root); // 第一个元素为root节点
        int i = 1; // 标记后续处理的节点值（包含null）
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            // 从队列中取出节点，然后根据是否为null，依次设置left和right
            // 如果不是null，则需要加入队列，后续需要处理此有效节点的左右节点
            if (vals[i].equals("null")) {
                tmp.left = null;
            } else {
                tmp.left = new TreeNode(Integer.valueOf(vals[i]));
                queue.offer(tmp.left);
            }
            i++;
            if (i >= vals.length) return root;
            if (vals[i].equals("null")) {
                tmp.right = null;
            } else {
                tmp.right = new TreeNode(Integer.valueOf(vals[i]));
                queue.offer(tmp.right);
            }
            i++;
            if (i >= vals.length) return root;
        }

        return root;
    }

}

